package xio.leetcode.java;

import java.util.Arrays;
import java.util.List;


/**
 * 524. Longest Word in Dictionary through Deleting (Medium)
 * 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
 *
 * 示例 1:
 *
 * 输入:
 * s = "abpcplea", d = ["ale","apple","monkey","plea"]
 *
 * 输出:
 * "apple"
 * 示例 2:
 *
 * 输入:
 * s = "abpcplea", d = ["a","b","c"]
 *
 * 输出:
 * "a"
 * 说明:
 *
 * 所有输入的字符串只包含小写字母。
 * 字典的大小不会超过 1000。
 * 所有输入的字符串长度不会超过 1000。
 *
 * 思路：遍历 d ，找到一个可以从s得到，且长度最长且字典顺序最小的字符串；
 * 其中，字典序的比较在Java中直接通过String 自带的 compareTo 方法进行比较: s1.compareTo(s2) ，s1 字典序小就返回负数，否则正数；
 * 是否可以从 s 中得到，则可以通过双指针遍历思想来比较即可。
 */
public class LC524_FindLongestWord {
    public String findLongestWord(String s, List<String> d) {
        String longest = "";
        for (String ds : d) {
            if (ds.length() < longest.length() ||
                    (ds.length()==longest.length() && longest.compareTo(ds) <= 0)){
                continue;
            }
            if (isMatch(s,ds)){
                longest = ds;
            }
        }
        return longest;
    }

    /**
     * 字符串 ms 是否可以通过字符串 s 删除一些字符来得到
     */
    private boolean isMatch(String s, String ms){
        int i = 0;
        int j = 0;
        while (i < s.length() && j < ms.length()){
            if (s.charAt(i) == ms.charAt(j)){
                j++;
            }
            i++;
        }
        // j 走完了说明ms的字符都可以从 s 得到，否则说明不可以
        return j == ms.length();
    }

    public static void main(String... args){
        LC524_FindLongestWord flw = new LC524_FindLongestWord();
        String result  = flw.findLongestWord("abpcplea", Arrays.asList("ale","apple","monkey","plea"));
        System.out.println(result);
    }
}
